\documentclass[submission]{FPSAC2017}

\articlenumber{48}
\addbibresource{48_Ahlbach_Swanson.bib}

% Packages
\usepackage{amsmath}              % provides \underset, etc.
\usepackage{amssymb}              % provides more symbols like semidirect product
\usepackage{accents}              % provides \accentset, etc.; must be loaded after amsmath
\usepackage{amsopn,amssymb}       % provides \DeclareMathOperator, \mathbb, etc.
\usepackage{bm}                   % provides \bm for math bold greek letters
\usepackage{bbm}                  % provides \mathbbm, eg. for lower-case blackboard bold characters
\usepackage{enumerate}            % more powerful enumerate environments
\usepackage{microtype}            % nicer text spacing
\usepackage[intoc,refpage]{nomencl}         % make a symbol list
\usepackage{multicol}             % put lists with many short entries into multiple columns
\usepackage{setspace}             % \doublespacing, etc.
\usepackage{shuffle}              % provides \shuffle and \cshuffle
\usepackage{soul}                 % multi-line underlines
\usepackage{thmtools}             % interface to amsthm
\usepackage{tikz-cd}              % nice commutative diagrams; see cd environment below
\usetikzlibrary{calc}             % allow \let's in tikzpicture environments
\usetikzlibrary{positioning}      % allow "above = 1" syntax
\usepackage{xifthen}              % \ifthenelse, \isempty, etc.
\usepackage{hyperref}            % url's
\usepackage[enableskew]{youngtab}

% Math operators
\DeclareMathOperator{\Ab}{Ab}
\DeclareMathOperator{\alg}{-alg}
\DeclareMathOperator{\Ann}{Ann}
\DeclareMathOperator{\Ass}{Ass}
\DeclareMathOperator{\cdes}{cdes}
\DeclareMathOperator{\CDes}{CDes}
\DeclareMathOperator{\CDT}{CDT}
\DeclareMathOperator{\Ch}{ch}
\DeclareMathOperator{\Char}{char}
\DeclareMathOperator{\cHom}{\mathcal{H}\textit{om}}
\DeclareMathOperator{\code}{code}
\DeclareMathOperator{\codim}{codim}
\DeclareMathOperator{\coker}{coker}
\DeclareMathOperator{\col}{col}
\DeclareMathOperator{\comaj}{comaj}
\DeclareMathOperator{\cont}{cont}
\DeclareMathOperator{\cmaj}{cmaj}
\DeclareMathOperator{\CT}{CT}
\DeclareMathOperator{\cycle}{cycle}
\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\Des}{Des}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\exc}{exc}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\Fl}{Fl}
\DeclareMathOperator{\Flatten}{Flatten}
\DeclareMathOperator{\FP}{FP}
\DeclareMathOperator{\Flags}{Flags}
\DeclareMathOperator{\fl}{fl}
\DeclareMathOperator{\flex}{flex}
\DeclareMathOperator{\freq}{freq}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\GKdim}{GKdim}
\DeclareMathOperator{\gl}{gl}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\gldim}{gldim}
\DeclareMathOperator{\gr}{gr}
\DeclareMathOperator{\Gr}{Gr}
\DeclareMathOperator{\GUD}{GUD}
\DeclareMathOperator{\hgt}{ht}
\DeclareMathOperator{\Hilb}{Hilb}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\injdim}{injdim}
\DeclareMathOperator{\Int}{int}
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\Kdim}{Kdim}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\lex}{lex}
\DeclareMathOperator{\maj}{maj}
\DeclareMathOperator{\mbs}{mbs}
\DeclareMathOperator{\mmaj}{mmaj}
\DeclareMathOperator{\Mod}{mod}
\DeclareMathOperator{\nil}{nil}
\DeclareMathOperator{\NSYM}{NSYM}
\DeclareMathOperator{\NFD}{NFD}
\DeclareMathOperator{\ot}{\otimes}
\DeclareMathOperator{\period}{period}
\DeclareMathOperator{\Perm}{Perm}
\DeclareMathOperator{\Perms}{Perms}
\DeclareMathOperator{\PN}{PN}
\DeclareMathOperator{\Pre}{pre}
\DeclareMathOperator{\projdim}{projdim}
\DeclareMathOperator{\pt}{pt}
\DeclareMathOperator{\QH}{QH}
\DeclareMathOperator{\QSYM}{QSYM}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\RCDT}{RCDT}
\DeclareMathOperator{\Res}{Res}
\DeclareMathOperator{\Rings}{Rings}
\DeclareMathOperator{\row}{row}
\DeclareMathOperator{\RSK}{RSK}
\DeclareMathOperator{\rw}{rw}
\DeclareMathOperator{\sd}{sd}
\DeclareMathOperator{\Sets}{\textit{Sets}}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\sh}{sh}
\DeclareMathOperator{\Sh}{Sh}
\DeclareMathOperator{\SIT}{SIT}
\DeclareMathOperator{\SL}{SL}
\DeclareMathOperator{\SO}{SO}
\DeclareMathOperator{\sort}{sort}
\DeclareMathOperator{\Sp}{Sp}
\DeclareMathOperator{\Span}{Span}
\DeclareMathOperator{\spec}{spec}
\DeclareMathOperator{\spin}{spin}
\DeclareMathOperator{\St}{St}
\DeclareMathOperator{\Stab}{Stab}
\DeclareMathOperator{\str}{str}
\DeclareMathOperator{\Supp}{Supp}
\DeclareMathOperator{\SST}{SST}
\DeclareMathOperator{\SSYT}{SSYT}
\DeclareMathOperator{\stat}{stat}
\DeclareMathOperator{\std}{std}
\DeclareMathOperator{\syt}{syt}
\DeclareMathOperator{\SYT}{SYT}
\DeclareMathOperator{\SYM}{SYM}
\DeclareMathOperator{\Sym}{Sym}
\DeclareMathOperator{\ssum}{ssum}
\DeclareMathOperator{\Sum}{sum}
\DeclareMathOperator{\TL}{TL}
\DeclareMathOperator{\Tot}{Tot}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\trdeg}{trdeg}
\DeclareMathOperator{\UD}{UD}
\DeclareMathOperator{\wgt}{wgt}
\DeclareMathOperator{\word}{word}
\DeclareMathOperator{\Words}{Words}
\DeclareMathOperator{\x}{\times}
\DeclareMathOperator{\YUD}{YUD}
% Named ``ilim'' for ``inverse limit'' to avoid conflicting with \lim
\newcommand{\ilim}{\operatornamewithlimits{\underset{\longleftarrow}{lim}}}
% ``dlim'' for ``direct limit''
\newcommand{\dlim}{\operatornamewithlimits{\underset{\longrightarrow}{lim}}}
\newcommand{\mbinom}[2]{\left(\!\!\binom{#1}{#2}\!\!\right)}

% Convenient shortcuts
\newcommand{\bA}{\mathbb{A}}
\newcommand{\bC}{\mathbb{C}}
\newcommand{\bE}{\mathbb{E}}
\newcommand{\bF}{\mathbb{F}}
\newcommand{\bk}{\mathbbm{k}}
\newcommand{\bN}{\mathbb{N}}
\newcommand{\bP}{\mathbb{P}}
\newcommand{\bQ}{\mathbb{Q}}
\newcommand{\bR}{\mathbb{R}}
\newcommand{\bZ}{\mathbb{Z}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\fg}{\mathfrak{g}}
\newcommand{\fm}{\mathfrak{m}}
\newcommand{\fn}{\mathfrak{n}}
\newcommand{\fp}{\mathfrak{p}}
\newcommand{\fq}{\mathfrak{q}}
\newcommand{\fS}{\mathfrak{S}}
\newcommand{\fU}{\mathfrak{U}}
\newcommand{\tsub}{\mathrel{\unlhd}}

% Convenient general macros
\newcommand{\up}{\mathord{\uparrow}}
\newcommand{\Ind}{\mathord{\uparrow}}
\newcommand{\down}{\mathord{\downarrow}}
\renewcommand{\star}{\mathord{*}}
\newcommand{\too}[1]{\stackrel{#1}{\to}}
\newcommand{\tooo}[2]{\underset{#2}{\overset{#1}{\to}}}
\newcommand{\oo}[3]{\underset{#3}{\overset{#2}{#1}}}
\newcommand{\sline}{\noindent\makebox[\linewidth]{\rule{\linewidth}{0.4pt}}}
\newcommand{\mdy}[1]{\sline\vspace{0.19cm}\\\centering{\Large{\textbf{#1}}}\\\sline}
\newcommand{\ind}{\!\!\uparrow}
\newcommand{\res}{\!\!\downarrow}
\newcommand{\f}{\frac}
\newcommand{\n}{\f{1}{n}}
\newcommand{\lm}{\lambda}
\newcommand{\lam}{\lambda}
\newcommand{\pa}[1]{{\left( {#1}\right)}}
\newcommand{\ha}{\f{1}{2}}
\newcommand{\sub}{\subset}
\newcommand{\al}{\alpha}
\newcommand{\8}{\infty}
\newcommand{\es}{\emptyset}
\newcommand{\bs}{\bigskip}
\newcommand{\D}{\Delta}
\newcommand{\de}{\delta}
\newcommand{\be}{\beta}
\newcommand{\w}{\omega}
\newcommand{\s}{\sigma}
\newcommand{\si}{\sigma}
\newcommand{\g}{\gamma}
\newcommand{\dd}{\cdot}
\newcommand{\zhat}{\widehat{0}}
\newcommand{\ohat}{\widehat{1}}
\newcommand{\idd}{\accentset{\bullet}{\iota}}
\newcommand{\nur}{\overset{\to}{\nu}}
\newcommand{\nul}{\overset{\gets}{\nu}}
\newcommand{\wt}[1]{\widetilde{#1}}
\newcommand{\tx}{\text}
\newcommand{\ti}{\tilde}
\newcommand{\sm}{\setminus}
\newcommand{\lp}{\left(}
\newcommand{\rp}{\right)}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\ch}{\binom}
\newcommand{\imp}{\implies}
\newcommand{\va}{\varphi}
\newcommand{\udot}{\dot{\,}}
\newcommand{\mch}[2]{%
  \left.\mathchoice%
    {\left(\kern-0.48em\ch{#1}{#2}\kern-0.48em\right)}
    {\left(\kern-0.30em\ch{\smash{#1}}{\smash{#2}}\kern-0.30em\right)}
    {\left(\kern-0.30em\ch{\smash{#1}}{\smash{#2}}\kern-0.30em\right)}
    {\left(\kern-0.30em\ch{\smash{#1}}{\smash{#2}}\kern-0.30em\right)}
  \right.
}


% rc-graph macros
\font\co=lcircle10
\def\petit#1{{\scriptstyle #1}}
\def\pes#1#2{\hbox{\rlap{$\petit {#1}_{\scriptscriptstyle #2}$}}
    \phantom{\petit 1}}
\def\plb{\smash{\lower2pt\hbox{\rlap{\vrule height12pt}}
                \raise2pt\hbox{\rlap{\hskip-4pt
                \vrule height.4pt depth0pt width14.7pt}}}}
\def\py{\smash{\raise2pt\hbox{\co \rlap{\rlap{\char'005} \char'007}}
               \raise6pt\hbox{\rlap{\vrule height4.5pt}}
               \raise2pt\hbox{\rlap{\hskip4pt \vrule height0.4pt depth0pt 
                              width6.5pt}}}}
\def\pe{\smash{\raise2pt\hbox{\co \rlap{\rlap{\char'005}
                 \phantom{\char'007}}}
               \raise6pt\hbox{\rlap{\vrule height4.5pt}}}}

% Mark Haiman's tableaux macro, modified to put dashed lines around empty boxes
\setlength{\unitlength}{0.06em}
\newlength{\cellsize} \setlength{\cellsize}{18\unitlength}
\newsavebox{\cell}
\sbox{\cell}{\begin{picture}(18,18)
\put(0,0){\line(1,0){18}}
\put(0,0){\line(0,1){18}}
\put(18,0){\line(0,1){18}}
\put(0,18){\line(1,0){18}}
\end{picture}}
\newsavebox{\dashedcell}
\sbox{\dashedcell}{\begin{picture}(18,18)
\multiput(0,0)(5,0){4}{\line(1,0){3}}
\multiput(0,0)(0,5){4}{\line(0,1){3}}
\multiput(18,0)(0,5){4}{\line(0,1){3}}
\multiput(0,18)(5,0){4}{\line(1,0){3}}
\end{picture}}
\newcommand\cellify[1]{\def\thearg{#1}\def\nothing{}%
\ifx\thearg\nothing
\hbox to 0pt{\usebox{\dashedcell} \hss}\else%
\hbox to 0pt{\usebox{\cell} \hss}\fi%
\vbox to \cellsize{
\vss
\hbox to \cellsize{\hss$#1$\hss}
\vss}}
\newcommand\tableau[1]{\vtop{\let\\\cr
\baselineskip -16000pt \lineskiplimit 16000pt \lineskip 0pt
\ialign{&\cellify{##}\cr#1\crcr}}}

\newenvironment{cd}[1][]
  {\begin{center}\begin{tikzcd}[#1]}
  {\end{tikzcd}\end{center}}

% Index/nomenclature configuration and macros
\renewcommand\nomname{List of Symbols}
\newcommand{\bu}[2][]{\framebox{#2}\ifthenelse{\isempty{#1}}{\index{#2}}
    {\index{#1@#2}}}
\newcommand{\mbu}[3][]{\boxed{#2}\nomenclature[$#1$]{$#2$}{#3}}

% Section macros
\newcommand{\Section}[1]{\begin{samepage}\sline\vspace{-0.5cm}\section*{\centering{#1}}\vspace{-0.5cm}\sline
  \addcontentsline{toc}{subsection}{#1}\end{samepage}}
\newcommand{\Subsection}[1]{\subsection*{\centering\color{teal}#1}
  \addcontentsline{toc}{subsection}{#1}}
\newcommand{\Subsubsection}[1]{\subsubsection*{\centering\color{teal}#1}
  \addcontentsline{toc}{subsubsection}{#1}}

% Modify standard distance between paragraphs; makes them look much better inside
%   ntheorem environments
%\setlength{\parskip}{0.3cm}

\theoremstyle{plain}
\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{Fact}[Theorem]{Fact}
\newtheorem{Conjecture}[Theorem]{Conjecture}
\newtheorem{Question}[Theorem]{Question}
\newtheorem{Problem}[Theorem]{Open Problem}

\theoremstyle{definition}
\newtheorem{Notation}[Theorem]{Notation}
\declaretheorem[style=definition,sibling=Theorem]{Definition}
\newtheorem{Example}[Theorem]{Example}
\newtheorem{Remark}[Theorem]{Remark}
\newtheorem{Aside}[Theorem]{Aside}
\newtheorem*{Summary}{Summary}
\newtheorem*{Outline}{Outline}


\title{Refined Cyclic Sieving}
\author{Connor Ahlbach \and Joshua P. Swanson}
\address{University of Washington, Seattle, USA\\}

\received{November 13th, 2016}

\abstract{
  Reiner-Stanton-White (2004) defined the cyclic sieving phenomenon
  (CSP) associated to a finite cyclic group action and polynomial. A key
  example arises from the length generating function for minimal length coset
  representatives of a parabolic quotient of a finite Coxeter group. In type
  $A$, this result can be phrased in terms of the natural cyclic action on
  words of fixed content.
  
  There is a natural notion of \textit{refinement} for
  many CSP's. We formulate and prove a refinement of the aforementioned CSP
  arising from tracking the \textit{cyclic descent type} of a word in addition
  to its content. The argument presented is completely different from
  Reiner-Stanton-White's representation-theoretic approach. It is
  combinatorial and largely, though not entirely, bijective.
  
  A building block of our argument involves cyclic sieving for shifted subset
  sums, which also appeared in Reiner-Stanton-White. We
  give an alternate, largely bijective proof of a refinement of this
  result by extending some ideas of Wagon-Wilf (1994).
}

\keywords{cyclic sieving phenomenon, $q$-binomial coefficients, major
index, words}


\begin{document}

\maketitle

\section{Introduction}
\label{sec:intro}

Since Reiner, Stanton, and White introduced the \textit{cyclic sieving phenomenon} (CSP) in 2004 \cite{MR2087303}, the cyclic sieving phenomenon has become an important companion to any cyclic action on a finite set. Some remarkable examples of the CSP involve the action of a Springer regular element on Coxeter groups
\cite[Theorem~1.6]{MR2087303}, the action of Schutzenberger's promotion on Young
tableaux of fixed rectangular shape \cite{MR2557880}, and the creation of new CSPs from old using multisets and plethysms with homogeneous symmetric functions \cite[Proposition 8]{MR2837599}. See \cite{MR2866734} for a thorough introduction to the cyclic sieving phenomenon by Sagan.

\begin{Definition}
  \label{def:csp1}
  Suppose $C_n$ is a cyclic group of order $n$ generated by $\sigma_n$, $W$ is
  a finite set on which $C_n$ acts, and $f(q) \in \bN[q]$. We say the triple
  $(W, C_n, f(q))$ exhibits the
  \textit{cyclic sieving phenomenon (CSP)} if for all $k \in \bZ$,
  \begin{align}
    \label{CSP1}
      \# W^{\si_n^k} := \# \{ w \in W: \si_n^k \dd w = w \} = f(\w_n^k),
  \end{align}
  where $ \w_n $ is a fixed primitive $ n $-th root of unity.
\end{Definition}

Our main result, \cref{thm:alpha_delta}, is a refinement of the type $A$ case of
\cite[Theorem~1.6]{MR2087303}, which we now summarize; see \Cref{sec:comb}
for missing definitions. Consider words in the alphabet $\bP := \{1, 2,
\ldots\}$. Given a word $w = w_1\cdots w_n$, let $\cont(w)$
denote the \textit{content} of $w$ and write
\begin{align} 
  W_\alpha := \{\text{words }w : \cont(w) = \alpha\} 
\end{align}
for the set of words with content $\alpha \vDash n$. Write $\maj(w)$ for the
\textit{major index} of $w$. The cyclic group $C_n$ acts on $W_\alpha$ by
rotation.

In many instances of cyclic sieving, $f(q)$ is a statistic generating
function on a set $ W $. Given a statistic $\stat \colon W \to \bN$, we form the generating function
\begin{align}
\label{eqn:gfnotation}
    W^{\stat}(q) := \sum_{w \in W} q^{\stat w} \in \bN[q]. 
\end{align}    
We say two statistics $ \stat, \stat': W \to \bN $ are \emph{equidistributed} on $ W $ if $ W^{\stat}(q) = W^{\stat'}(q) $. The following expresses an interesting result of Reiner, Stanton, and White in our notation.

\begin{Theorem}\cite[Proposition~4.4]{MR2087303}
  \label{thm:rsw_alpha}
  Let $\alpha \vDash n$. The triple $(W_\alpha, C_n, W_\alpha^{\maj}(q))$
  exhibits the CSP.
\end{Theorem}

\begin{Definition}
  A \textit{refinement} of a CSP triple $(W, C_n, W^{\stat}(q))$ is a CSP
  triple $(V, C_n, V^{\stat}(q))$ where $V \subset W$ has the restricted
  $C_n$-action.
\end{Definition}

If $(V, C_n, V^{\stat}(q))$ refines $(W, C_n, W^{\stat}(q))$, then so does $(U, C_n, U^{\stat}(q)) $, where $ U = W - V $. Thus a refinement partitions $ W $ into smaller CSPs with the same statistic. In \Cref{sec:flex}, we define a statistic on words, \textit{flex}, which is universal in the sense that it refines to all $ C_n $-orbits. Such universal statistics are essentially equivalent to the choice of total orderings for each orbit $\cO$ of $W$.

We partition words of fixed content into fixed
\textit{circular descent type} ($ \CDT $). One
computes $\CDT(w)$ by building up $w$ through adding all $1$'s, $2$'s,
$\ldots$, and counting the number of \textit{circular descents} introduced at
each step. See \Cref{sec:runs} for the precise definition. We
write the set of words with fixed content and circular descent type as
\begin{align} 
\label{eqn:fixedcontCDT}
    W_{\alpha,\delta} := \{\text{words }w : \cont(w) = \alpha, \CDT(w) = \delta\}. 
\end{align}

\begin{Theorem}
  \label{thm:alpha_delta}
  Let $ \alpha \vDash n $, and let $ \de $ be any weak composition. The triple
    \[ (W_{\alpha,\delta}, C_n, W_{\alpha,\delta}^{\maj}(q)) \]
exhibits the CSP.
\end{Theorem}

\noindent Indeed, we derive an explicit product formula for
$W_{\alpha,\delta}^{\maj}(q)$ mod $(q^n - 1)$ involving $q$-binomial
coefficients, see \Cref{thm:Maj GF Mod n}.

Reiner-Stanton-White's proof of \Cref{thm:rsw_alpha} builds on a
representation-theoretic result due to Springer \cite[Proposition 4.5]{MR0354894}. For \Cref{thm:alpha_delta},
we have instead considered the problem of finding a bijective proof, which we
interpret precisely as the problem of finding a bijective proof that $\flex$
and $\maj$ are equidistributed mod $n$ on $W_{\alpha,\delta}$. Our argument
is highly combinatorial, but it is not entirely bijective. Finding an explicit
bijection would be quite interesting.

A key building block of our proof of \Cref{thm:alpha_delta} involves cyclic
sieving on subsets. We describe a refinement of this result,
\Cref{thm:Fixedgcds}, by restricting to subsets satisfying certain
gcd requirements.

The rest of this extended abstract is organized as follows. In
\Cref{sec:comb}, we recall combinatorial background. In \Cref{sec:flex}, we
define the flex statistic. In \Cref{sec:runs}, we decompose words with
fixed content and circular descent type and summarize proofs of the product formula, \Cref{thm:Maj GF Mod n}, and our main result, \Cref{thm:alpha_delta}.
\Cref{sec:subsets} gives an alternative proof of refined cyclic sieving on subsets using a method inspired by Wagon-Wilf \cite{MR1269164}. Many of the proofs are omitted or summarized due to space constraints. They will be included in a forthcoming version of this article \cite{as16}.

\section{Combinatorial Background}
\label{sec:comb}

In this section, we briefly introduce combinatorial notions on words
and fix our notation. We use the alphabet of positive integers $\bP
:= \{1, 2, \ldots\}$ throughout. A \emph{word} $w$ of length $ n $ is a sequence $ w = w_1 w_2 \cdots w_n $
of \textit{letters} $w_i \in \bP$. Let $ |w| $ denote the length of a word
$ w $. The \textit{descent set} of $w$ is $\Des(w) :=
\{1 \leq i < n : w_i > w_{i+1}\}$ and the number of descents is $\des(w) :=
\# \Des(w)$. The \textit{major index} of $w$ is $\maj(w) :=
\sum_{i \in \Des(w)} i$. The \textit{inversion number} of $ w $ is $ \inv(w) := \# \{ 1 \le i < j \le n : w_i > w_j \} $. The \textit{cyclic descent set} of $w$ is $\CDes(w)
:= \{1 \leq i \leq n : w_i > w_{i+1}\}$, where now the subscripts are taken
mod $n$, and $\cdes(w) := \#\CDes(w)$. We use lower dots
between letters to indicate cyclic descents and upper dots to indicate cyclic
ascents throughout the paper, as in the following example.

\begin{Example}
  If $w = 155.3.155.3. = 1\udot5\udot531\udot5\udot53 $, then
  $|w| = 8$, $\Des(w) = \{ 3, 4, 7 \}$,
  $ \des(w) = 3 $, $\CDes(w) = \{3, 4, 7, 8\}$, $ \cdes(w) = 4 $,
  $\maj(w) = 14$, and $\inv(w) = 9$.
\end{Example}

A \textit{composition} or \textit{weak composition} of $n$ is a finite sequence $(\alpha_1, \alpha_2, \ldots, \alpha_m)$ of non-negative integers adding up to $n$, typically denoted $\alpha \vDash n$. A \textit{strong composition} additionally requires each $\alpha_i \neq 0$. The \textit{content} of a word $ w $, denoted $ \cont(w) $, is the sequence $ \al $ whose $ j $-th part is the number of $ j $'s in $ w $. For a word $ w $ of length $ n $, $ \cont(w) $ is a weak composition of $ n $. We write
\begin{align}
  W_n &:= \{\text{words }w : |w| = n\}, \\
  W_\alpha &:= \{w \in W_n : \cont(w) = \alpha \}.
\end{align}
The cyclic group $ C_n := \langle \si_n \rangle$ of order $ n $ acts on
$ W_n $ and $ W_\al $ by
\begin{equation*}
  \si_n \cdot w_1 \cdots w_{n-1} w_n := w_n w_1 \cdots w_{n-1}.
\end{equation*}

The set of all words in $\bP$ is a monoid under concatenation. A word is
\textit{primitive} if it is not a power of a smaller word. Any non-empty word
$w$ may be written uniquely as $w = v^f$ for $f \geq 1$ with $ v $ primitive.
We call $ |v| $ the \textit{period} of $w$, written $ \period(w) $, and
$f$ the \textit{frequency} of $w$, written $\freq(w)$. The orbit of $ w \in W_n $
under rotation is a \emph{necklace}, usually denoted $[w]$. We have
$\period(w) = \#[w]$ and $ \freq(w) \dd \period(w) = |w|$. Content,
primitivity, period, frequency, and $\cdes$ are all constant on necklaces.

\begin{Example}
  \label{ex:necklace}
  The necklace of $w = 15531553 = (1553)^2$ is
  \[
    [w] := \{15531553, 55315531, 53155315, 31553155 \} \sub W_{(2, 0, 2, 0, 4)} \sub W_8,
  \]
  which has period $4$, frequency $2$, and $\cdes$ $4$.
\end{Example}

Reiner-Stanton-White gave several equivalent conditions for a triple
$(W, C_n, f(q))$ to exhibit the CSP. In place of \eqref{CSP1} in
\Cref{def:csp1}, we may instead require
\begin{align}
  \label{CSP2}
    f(q) \equiv \sum_{\text{orbits }\cO \subset W } \;
      \frac{q^n - 1}{q^{n/|\cO|} - 1} \quad (\Mod q^n - 1),
\end{align}
where the sum is over all orbits $ \cO $ under the action of $ C_n $ on $ W $, and for $ d \mid n $,
\begin{align} 
    \frac{q^n - 1}{q^d - 1} = \sum_{i=0}^{n/d - 1} q^{id}
     \not\equiv 0 \; (\Mod q^n - 1). 
\end{align}
We refer the interested reader to \cite[Proposition 2.1]{MR2087303} for the proof of the equivalence of \eqref{CSP1} and \eqref{CSP2}.

For a set $S$, write
\begin{align*}
  \ch{S}{k} := \{\text{$k$-element subsets of $S$}\}, \;
  \mch{S}{k} := \{\text{$k$-element multisubsets of $S$}\}.
\end{align*}
We use the following $q$-analogues for $ n, k \in \bZ_{\ge 0} $, where "$ \Sum $'' is the sum of the elements in a set or multiset:
\begin{align}
    [n]_q & = 1 + q + \dots + q^{n - 1}, \\
    [n]_q! & = [n]_q [n - 1]_q \dots [1]_q, \\
    \binom{n}{\al_1, \dots, \al_m}_q & = \f{[n]_q!}{[\al_1]_q! \dots [\al_m]_q!}, \\
    \label{eqn:sum_subsets}
    \binom{n}{k}_q & = \binom{n}{k, n - k}_q = q^{-\binom{k}{2}} \ch{[0,n - 1]}{k}^{\Sum}(q), \\
    \mch{n}{k}_q & = \binom{n + k - 1}{k}_q = \mch{[0,n - 1]}{k}^{\Sum}(q).
\end{align}

For $ \al = (\al_1, \dots, \al_m) \vDash n $, $ \maj $ and $ \inv $ are equidistributed on $ W_\al $ with
\begin{align}
\label{eqn:macmahon}
    W_\al^{\maj}(q) = W_\al^{\inv}(q) = \binom{n}{\al_1, \dots, \al_m}_q
\end{align}
by a classical result of MacMahon \cite{MR1576566}. Despite \eqref{eqn:macmahon}, $ \maj $ and $ \inv $ are not equidistributed modulo $ n $ on $ W_{\al,\de} $ in general, so $ (W_{\al,\de}, C_n, W_{\al,\de}^{\inv}(q)) $ does not exhibit the CSP.

\section{The Flex Statistic}
\label{sec:flex}

\begin{Definition}
  Let $\lex(w)$  denote the index at which $w$ appears when lexicographically
  ordering the necklace $[w]$, starting from $0$. Let \textit{flex} be the
  product
    \[ \flex(w) := \freq(w) \lex(w). \]
\end{Definition}

\noindent For example, the necklace in \Cref{ex:necklace} has $\lex$ statistics
$0, 3, 2, 1$, respectively, so that $\lex(55315531) = 3$ and
$\flex(55315531) = 2 \cdot 3 = 6$. The following is a direct consequence of \eqref{CSP2}.

\begin{Lemma}
  \label{lem:univCSP}
  For any necklace $ N $ of length $n$, $ (N, C_n, N^{\flex}(q)) $
  exhibits the CSP.
\end{Lemma}

Thus, for any set $ W \sub W_n $ on which $ C_n $ acts,
$ (W, C_n, W^{\flex}(q)) $ exhibits the CSP. In this sense, $\flex$ is a
``universal CSP statistic on words''. By contrast, for instance when $N = [123123]$,
the triple $(N, C_6, N^{\maj}(q))$ does not exhibit the CSP. In this sense,
$\maj$ is a not a universal CSP statistic on words. Indeed, it follows from \Cref{lem:univCSP} that \Cref{thm:alpha_delta} is equivalent to $ \maj $ and flex being
equidistributed modulo $ n $ on $ W_{\al,\de} $. It would be interesting to find a natural,
explicit bijection proving this version of \Cref{thm:alpha_delta}.

\begin{Problem}
  For $ \al \vDash n $ and any composition $\delta$, find a bijection
  $ \va: W_{\al, \de} \to W_{\al, \de} $ satisfying
  \begin{align}
    \maj(\va(w)) \equiv \flex(w) \;(\Mod n).
  \end{align}
\end{Problem}

\section{Cyclic Descent Type and Major Index}
\label{sec:runs}

The main purpose of this section is to give a product formula for $ W_{\al,\de}^{\maj}(q) $ modulo $ q^n - 1 $, \Cref{thm:Maj GF Mod n}. The $ q = 1 $ specialization gives a formula for $ \# W_{\al,\de} $, \Cref{lem:W_alpha_delta_count}. We conclude this section by summarizing our proof of the main result, \Cref{thm:alpha_delta}, given \Cref{thm:Maj GF Mod n}.

\subsection{Cyclic Descent Type}

We begin by defining cyclic descent type.
Throughout this section, $ w $ is a word with $ \cont(w) = \al = (\al_1,
\ldots, \al_m) $, a strong composition of $ n \ge 1 $, and $ k $ circular descents, so that $ m = \max(w) $. Let $ w^{(i)} $ denote the subsequence of $ w $ with all elements
larger than $ i $ removed. We have a ``filtration''
\[
	\varnothing \preceq 1^{\al_1} = w^{(1)} \preceq w^{(2)}
        \preceq \dots \preceq w^{(m - 1)} \preceq w^{(m)} = w,
\]
where $ u \preceq v $ means that $ u $ is a subsequence of $ v $. The
\textit{cyclic descent type} of a word $ w $, denoted $ \CDT(w) $, is the
sequence which tracks the number of new cyclic descents at each stage of the
filtration:
\begin{align}
\label{eqn:CDT}
	\CDT(w) := (\cdes w^{(1)}, \cdes w^{(2)} - \cdes w^{(1)}, \dots,
                \cdes w^{(m)} - \cdes w^{(m - 1)} ).
\end{align}
Note $ \CDT $ is constant on necklaces since rotating $ w $ rotates each
$ w^{(i)} $. Also, $ \CDT(w) $ is a weak composition of $ \cdes(w) = k $. Recall our earlier notation \eqref{eqn:fixedcontCDT}:
\begin{align*}
  W_{\alpha, \delta}
    &:= \{w \in W_n : \cont(w) = \alpha, \CDT(w) = \delta\}.
\end{align*}

\begin{Example}
Suppose $ w = 143124114223 $, so $\cont(w) = (4, 3, 2, 3)$,
  \begin{align*}
    & w^{(1)} = 1111              & \cdes w^{(1)} = 0, \\
    & w^{(2)} = 112.1122.         & \cdes w^{(2)} = 2, \\
    & w^{(3)} = 13.12.11223.      & \cdes w^{(3)} = 3, \\
    & w^{(4)} = 14.3.124.114.223. & \cdes w^{(4)} = 5.
  \end{align*}
  Hence, $\CDT(143124114223) =
  (0, 2-0, 3-2, 5-3) = (0, 2, 1, 2)$.
\end{Example}

\subsection{Runs, Falls, and Major Index}

We describe a way to create words
with a fixed content and CDT in terms of insertions into \textit{runs} and
\textit{falls}. We organize this procedure into a tree whose edges are labelled by sets and multisets
(\Cref{def:tree}).
\Cref{prop:maj_triple} describes changes in the major index upon traversing an
edge of this tree, which gives \Cref{thm:Maj GF Mod n} when iteratively applied.

\begin{Definition}
A \textit{fall} in $w$ is a maximal set of
  distinct indexes $i, i+1, \ldots, j-1, j$ such that $w_i > w_{i+1} > \cdots >
  w_j$, where we take indices modulo $ n $. A \textit{run}
  in a non-constant word $w$ is a maximal set of distinct indexes $i, i+1,
  \ldots, j$ such that $w_i \leq w_{i+1} \leq \cdots \leq w_j$, where we take
  indices modulo $ n $. The constant word $w = \ell^n$ by convention has no
  runs, though this case will not actually appear in our arguments.
\end{Definition}

Each letter is part of a unique run and a unique fall, except when
$ w = \ell^n $ is constant. It is easy to see that with these conventions,
$w$ has $n - \cdes(w)$ falls and $\cdes(w)$ runs. We index falls from $0$
starting at the fall containing the first letter of $w$, and we do the same
with runs.

\begin{Example}
  Let $w = 26534611 = 26.5.346.11 = 2\udot653\udot4\udot61\udot1\udot$, where
  lower dots indicate cyclic descents and upper dots indicate cyclic weak
  ascents. The three runs of $w$ are $1126, 5, 346$, with
  respective indexes $0, 1, 2$. The five falls of $ w $ are
  $ 2, 653, 4, 61, 1 $ with respective indexes $0, 1, 2, 3, 4$.
\end{Example}

\begin{Definition}
  Fix a letter $\ell$ not in $ w $. Pick a subset $ F $ of the falls of $w$. We
  \textit{insert $\ell$ into the falls $F$} by successively
  inserting $\ell$ into each fall $w_i > w_{i+1} > \cdots > w_j$ in $ F $ so
  that $ w_i \cdots \ell \cdots w_j $ is still decreasing.
  
  Similarly, we may fix a letter $\ell$ and pick a \textit{multisubset} $R$ of
  the runs of $w$. We \textit{insert $\ell$ into the runs $R$} by
  successively inserting $\ell$ into each run $w_i \leq w_{i+1} \leq \cdots
  \leq w_j$ in $R$ so that $ w_i \cdots \ell \cdots w_j $ is still weakly
  increasing.
  
  In either case, if we have a choice between inserting a letter at either
  the beginning of $w$ or at the end of $w$, we choose to insert at the
  beginning of $w$. When inserting $\ell$ into a run already containing
  $\ell$, the resulting word is independent of precisely which of the
  possible positions is used.
\end{Definition}

\begin{Example}
  Let $w = 2\udot653\udot4\udot61\udot1\udot$. Insert $7$ into the falls of $w$
  with indexes $0$ and $3$ to successively obtain
  $\underline{7}2\udot653\udot4\udot61\udot1\udot$ and then $w' :=
  72\udot653\udot4\udot\underline{7}61\udot1\udot$. Note that $w'=
  7.26.5.347.6.11$ has two more runs than $w$. Now insert
  $7$ into the runs of $w'$ with multiset of indexes $\{0,2,3,3\}$ to successively
  obtain $\underline{7}7.26.5.347.6.11$, $77.26.5\underline{7}.347.6.11$, $ 77.26.57.347.6.11$, and $ w'' := 77.26.57.34\underline{7}7.6.11 $.
\end{Example}

It will shortly prove convenient to restrict to words ending in a $1$. Let
\begin{align*}
    \widetilde{W}_n
      &= \{ w \in W_n : w \tx{ ends in a 1} \}, \\
    \widetilde{W}_{\al, \de}
      &= \{ w \in W_{\al, \de} : w \tx{ ends in a 1} \}.
\end{align*}
Inserting a letter into a subset of the falls and then a multisubset of the runs forms the basis of our procedure
for constructing words in $\widetilde{W}_{\alpha, \delta}$.

\begin{Definition}
  Fix $ w \in \widetilde{W}_n $, a letter $\ell$ not in $ w $, and
  \[ F \subset [0, |w| - \cdes w - 1]
       \qquad \text{and} \qquad
     R \underset{\text{mult.}}{\subset} [0, \cdes w + |F| - 1] \]
  where $\underset{\text{mult.}}{\subset}$ denotes a multisubset.
  Let $w'$ be obtained by inserting $\ell$
  into falls $F $ of $w$, and let $w''$ be obtained by inserting $\ell$ into
  runs $ R $ of $w'$. We say $w''$ is obtained by \textit{inserting
  the triple} $(\ell, F, R)$ into $w$. In particular,
  $\cdes w'' = \cdes w + |F|$. By keeping track of the effect of each insertion on maj, one can show the following.
\end{Definition}

\begin{Lemma}
  \label{prop:maj_triple}
  Suppose $w''$ is obtained by inserting the triple $(\ell, F, R)$ into $w \in
  \widetilde{W}_n $. Then,
    \begin{align} \maj(w'') - \maj(w) = \binom{|F|+1}{2} + (\cdes w)(|F| + |R|)
         + |F||R| + \sum_{f \in F} f - \sum_{r \in R} r. \end{align}
\end{Lemma}

\begin{Definition}
  \label{def:tree}
  Fix a strong composition $\alpha $ of $ n $ and $ \delta \vDash k $, and let $ n_\ell := \al_1 + \dots + \al_\ell $ and
  $ k_\ell := \delta_1 + \dots + \delta_\ell $. Construct a rooted, vertex- and edge-labeled tree
  $T_{\alpha,\delta}$ recursively as follows. Begin with root
  $1^{\alpha_1}$. For $\ell=2, 3, \ldots$, for each leaf $w$, and
  for each triple $(\ell, F, R)$ with
    \[ F \in \binom{[0, n_{\ell - 1} - k_{\ell - 1} - 1]}{\delta_{\ell}} \qquad \text{and} \qquad
         R \in \mch{[0, k_{\ell}-1]}{\alpha_{\ell}-\delta_{\ell}}, \]
  add an edge labeled by $(\ell, F, R)$ from $w$ to $w''$ where $w''$ is 
  obtained by inserting the triple $(\ell, F, R)$ into $w$.
\end{Definition}

\begin{Example}
  \label{ex:tree}
  Let $\alpha = (4, 2, 3)$ and $\delta = (0, 2, 1)$. The following is the
  subgraph of $T_{\alpha,\delta}$ consisting of paths from the root to
  leaves that are rotations of $112113323$:

  \begin{center}
    \begin{tikzpicture}
      \node (2)  at (0, -4.5)  {$1111$};
      \node (3a) at (-2.5, -6) {$211211$};
      \node (3b) at (2.5, -6)  {$121121$};
      \node (4a) at (-4, -8) {$332311211$};
      \node (4b) at (-1.5, -8) {$211332311$};
      \node (4c) at (1.5, -8)  {$133231121$};
      \node (4d) at (4, -8)  {$121133231$};

      \draw [->] (2) -- (3a) node [midway, left]
        {$(2, \{0, 2\}, \varnothing)$};
      \draw [->] (2) -- (3b) node [midway, right]
        {$(2, \{1, 3\}, \varnothing)$};
      \draw [->] (3a) -- (4a) node [midway, left]
        {$(3, \{0\}, \{0, 1\})$};
      \draw [->] (3a) -- (4b) node [auto = left, pos = 0.35 ]
        {$(3, \{2\}, \{1, 2\})$};
      \draw [->] (3b) -- (4c) node [auto = right, pos = 0.9]
        {$(3, \{1\}, \{0, 1\})$};
      \draw [->] (3b) -- (4d) node [midway, right]
        {$(3, \{3\}, \{1, 2\})$};
    \end{tikzpicture}
  \end{center}
  For this full $T_{\alpha, \delta}$, the root has $\binom{4}{2} = 6$
  children since $1111$ has $4$ falls. Each child of the root itself has
  $\binom{4}{1}\mch{2}{2} = 12$ children. Hence, $T_{\alpha,\delta}$ has $72$
  leaves. The cyclic rotations of $112113323$ appearing as leaves in \Cref{ex:tree} are exactly those ending in $1$.
\end{Example}

\begin{Lemma}
  \label{lem:W_alpha_delta_count}
  Let $\alpha = (\alpha_1, \ldots, \alpha_m) $ be a strong composition
  of $ n $ and $\delta = (0, \delta_2, \ldots, \delta_m)\vDash k $.
  Then
  \begin{equation}
    \label{eq:W_alpha_delta}
    \# W_{\alpha, \delta}
       = \frac{n}{\alpha_1}
         \prod_{i=2}^{m} \binom{n_{i - 1} - k_{i - 1}}{\delta_{i}}
           \mch{k_{i}}{\alpha_{i} - \delta_{i}}
  \end{equation}
  In particular, $W_{\alpha, \delta} \neq \varnothing$ if and only if
  \begin{align*}
    0 &\leq \delta_i \leq \alpha_i
      &\text{for }1 \leq i \leq m, \\
    \delta_1 + \cdots + \delta_{i+1}
      &\leq \alpha_1 + \cdots + \alpha_i
      &\text{for }1 \leq i < m.
  \end{align*}
\end{Lemma}

\begin{Theorem}
\label{thm:Maj GF Mod n}
  Suppose $\alpha = (\al_1, \dots, \al_m) $ is a strong composition of $ n $ and $ \de = (\de_1, \dots, \de_m) \vDash k $. Set $ n_i := \al_1 + \dots + \al_i $, $ k_i := \delta_1 + \dots +
  \delta_i $, and $ d = \gcd(n,k) $. Then, modulo $ q^n - 1 $,
  \begin{align}
	  W_{\al,\de}^{\maj}(q)
        \equiv \f{d}{\al_1} \lp \frac{q^n - 1}{q^d - 1} \rp
	     q^{\ch{k}{2} + \sum_{i = 2}^m \ch{\de_i}{2} - \al_1 }
	     \prod_{i = 2}^m \ch{n_{i - 1} - k_{i - 1}}{\de_i}_q
	       \mch{k_i}{\al_i - \de_i}_q
  \end{align}
\end{Theorem}

\Cref{lem:W_alpha_delta_count} and \Cref{thm:Maj GF Mod n} are consequences of the structure of the tree $T_{\alpha, \delta}$ and \Cref{prop:maj_triple}.

\subsection{Proof Sketch of the Main Theorem}
\label{sec:CSP}

From the explicit formula in \Cref{thm:Maj GF Mod
n}, one may show the coefficient of $ q^i $ in $W_{\al,\de}^{\maj}(q) \, (\Mod q^n - 1) $ depends only on $ i $ modulo $ g := \gcd(\alpha_1, \ldots, \alpha_m, \delta_1, \ldots, \delta_m)$. We then show the triple $(W_{\alpha, \delta}, \la \si_n^{n/g} \ra,
W_{\alpha, \delta}^{\maj}(q))$ exhibits the CSP using products of CSP's on sets and multisets. Finally, we combine these two observations to extend this CSP to $ C_n $ to achieve \Cref{thm:alpha_delta}.

\section{A Refinement of the Cyclic Sieving Phenomenon on Subsets}
\label{sec:subsets}

Our proof of \Cref{thm:alpha_delta} uses products involving the following CSP
triples, first observed by Reiner, Stanton, and White.

\begin{Theorem}{\cite[Theorem 1.1]{MR2087303}}.
  \label{thm:csp_sms}
  Let $C_n$ act on $ \binom{[0, n-1]}{k} $ by
  incrementing values modulo $n$. Then
    \[ \left(\binom{[0, n-1]}{k}, C_n, \binom{n}{k}_q\right)
         \]
  exhibits the CSP.
\end{Theorem}

\noindent We refer the reader to Sections 3 and 4 of \cite{MR2087303} for
proofs of \Cref{thm:csp_sms} via representation theory or direct calculation,
respectively. We give an alternative proof inspired by a method of Wagon and
Wilf \cite[\S3]{MR1269164}, who characterized when the subset sum statistic is
equidistributed modulo $ m $. The main novelty of our approach is
\Cref{thm:Fixedgcds}, which gives a refinement of a related CSP
using a shifted sum statistic to subsets satisfying certain gcd
requirements. Throughout this section, we fix $n$ and $k$ and let
$S := \ch{[0, n-1]}{k}$.

\begin{Definition}
\label{defn:Craction}
  For all $ r \mid n $ and $ j \in [1, \f{n}{r} ] $, let
    \[ I_{r}^j := [(j - 1)r, jr - 1], \]
  which we call an \textit{$ r $-interval}. Let $ C_r $, the cyclic group of
  order $ r $, act on $ S = \binom{[0, n-1]}{k} $ by simultaneous rotation of
  $ r $-intervals. For example, when $n=k=6$, the generator for $C_3$ acts on
  the $6$-interval by the permutation $(012)(345)$. Finally, let
  \begin{align}
  \label{eqn:shiftedsum}
     \Sum'(A) := \sum_{a \in A} a - \sum_{i=0}^{k-1} i
              = \sum_{a \in A} a - \ch{k}{2}.
  \end{align}
Recall from \eqref{eqn:sum_subsets} that
  \begin{equation}
    \label{eq:sumprime}
    \ch{[0, n-1]}{k}^{\Sum'}(q) = \binom{n}{k}_q.
  \end{equation}
\end{Definition}

Using \eqref{eq:sumprime}, we may restate \Cref{thm:csp_sms} as saying that
$(S, C_n, S^{\Sum'}(q))$ exhibits the CSP, where $C_n$ acts on $S$ by rotation. Let $ C_r' $ denote the unique subgroup of size $ r $ in $ C_n $. The action of $C_r$ on $S$ in \Cref{defn:Craction} differs from this restricted action of $ C_r' $, but they are easily
seen to be isomorphic. Thus, $(S, C_r', S^{\Sum'}(q))$ exhibits the CSP as well. We will thus use the action of $C_r$ on $S$ in
\Cref{defn:Craction} for the rest of this section.

\begin{Definition}
  Let
  \[
     G_{a, b} = \{ A \in S :  \gcd(a, \#(A \cap I_{a}^1), \#(A \cap I_{a}^2),
                                   \ldots, \#(A \cap I_{a}^{n/a}) ) = b \}.
\]
In particular, $ G_{a,b} $ is empty unless $ b \mid a $. Also, for any divisibility chain $ D = d_p \mid d_{p - 1} \mid \dots \mid d_1 \mid n $, let
\begin{align}
    G_D = G_{n, d_1} \cap G_{d_1, d_2} \cap \dots \cap G_{d_{p - 1}, d_p}.
\end{align}
\end{Definition}

\begin{Example} If $ n = 4, k = 2 $, then
  \begin{align*}
    G_{1 \mid 2 \mid 4} = G_{4,2} \cap G_{2,1} & = \{ \{0, 2\}, \{0, 3\},\{1,2\}, \{1, 3\} \}, \\
    G_{2 \mid 2 \mid 4} = G_{4,2} \cap G_{2,2} & = \{ \{0, 1\}, \{ 2, 3\} \}.
  \end{align*}
\end{Example}

\begin{Theorem}
  \label{thm:Fixedgcds}
  Fix $n, k \in \bZ_{\geq 0}$, let $S := \binom{[0, n-1]}{k}$, and let $ D $ be a divisibility chain beginning with $ e \mid d $ and ending with $ n $. Then, $C_{d}$ acts on $S$ and $ G_D $ by simultaneous rotation of $d$-intervals, and
\[(G_D, C_{d}, G_D^{\Sum'}(q)) \]
  exhibits the CSP and refines the CSP triple $(S, C_{d}, S^{\Sum'}(q))$.
\end{Theorem}

\begin{Example}
  \label{ex:Gsumdist}
  Suppose $ n = 4, k = 2, D = 1\mid 2\mid 4$, so $G_D = G_{4,2} \cap G_{2,1} $. Then, $ G_D $ has $ C_2 $
  orbits $ \{ \{0, 2\}, \{1, 3\} \} $ and $ \{\{1,2\}, \{0, 3\} \} $ and
  \[
    G_D^{\Sum'}(q) = q^1 + 2q^2 + q^3 \equiv 2 \dd \f{q^2 - 1}{q - 1} \quad
    (\Mod q^2 - 1).
  \]
  Thus, $ (G_{1|2|4}, C_2, G_{1|2|4}^{\Sum'}(q)) $ exhibits the CSP.
\end{Example}

\Cref{thm:Fixedgcds} includes \Cref{thm:csp_sms} in the special case when $ D = \gcd(n,k) \mid n $. Our proof of \Cref{thm:Fixedgcds} proceeds by induction on $ d $. The cases where $ d = 1 $ or $ e = d $ are easy to verify on their own. Otherwise, we have $ e < d $, and we use the induction hypothesis to deduce $ (G_D, C_e, G_D^{\Sum'}(q)) $ exhibits the CSP.

In order to extend this CSP up to $ C_d $, we replace $ C_e $ by $ C_e' $, the unique subgroup of size $ e $ in $ C_d $, which is valid since the actions of $ C_e $ and $ C_e' $ on $ G_D $ are isomorphic. We then apply a straightforward extension lemma to prove \Cref{thm:Fixedgcds}.

\acknowledgements{
The authors would like to thank their advisor, Sara Billey, for her support and numerous helpful comments.
}

\printbibliography


\end{document}
